package impl;

import anaydis.sort.SorterType;
import org.jetbrains.annotations.NotNull;

import java.util.Comparator;
import java.util.List;

public class QuickSortWithCut extends AbstractQuickSorter {

    private final static int M = 6;
    private final InsertionSorter insertionSorter;

    public QuickSortWithCut() {
        super(SorterType.QUICK_CUT);
        insertionSorter = new InsertionSorter();
    }

    public <T> void sort(@NotNull Comparator<T> comparator,@NotNull List<T> list) {
        sort(comparator, list, 0, list.size() - 1, M);
    }

    public <T> void sort(Comparator<T> comparator, List<T> list, int M) {
        sort(comparator, list, 0, list.size() - 1, M);
    }

    private <T> void sort(Comparator<T> comparator, List<T> list, int left, int right, int M) {
        if (right <= left) return;
        if (right - left <= M) {
            insertionSorter.sort(comparator,list);
            return;
        }
        int i = partition(comparator, list, left, right);
        sort(comparator, list, left, i - 1, M);
        sort(comparator, list, i + 1, right, M);
    }
}